Linear congruence theorem Totally Explained

Everything about Linear Congruence Theorem totally explained

In modular arithmetic, the question of when a linear congruence can be solved is answered by the linear congruence theorem. If a and b are any integers and n is a positive integer, then the congruence:ax ≡ b (mod n) (1) has a solution for x if and only if b is divisible by the greatest common divisor d of a and n (denoted by gcd(a,n) | b). When this is the case, and x₀ is one solution of (1), then the set of all solutions is given by ť

System of linear congruences

By repeatedly using the linear congruence theorem, one can also solve systems of linear congruences, as in the following example: find all numbers x such that ť 2x ≡ 2 (mod 6)

3x ≡ 2 (mod 7) ť 2x ≡ 4 (mod 8)

By solving the first congruence using the method explained above, we find x ≡ 1 (mod 3), which can also be written as x = 3k + 1. Substituting this into the second congruence and simplifying, we get ť 9k ≡ −1 (mod 7)

Solving this congruence yields k ≡ 3 (mod 7), or k = 7l + 3. It then follows that x = 3 (7l + 3) + 1 = 21l + 10. Substituting this into the third congruence and simplifying, we get ť 42l ≡ −16 (mod 8)

which has the solution l ≡ 0 (mod 4), or l = 4m. This yields x = 21(4m) + 10 = 84m + 10, or ť x ≡ 10 (mod 84)

which describes all solutions to the system.

Further Information

Get more info on 'Linear Congruence Theorem'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://linear_congruence_theorem.totallyexplained.com">Linear congruence theorem Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.